package com.lw.leetcode.arr.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2359. 找到离给定两个节点最近的节点
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/2 9:31
 */
public class ClosestMeetingNode {

    public static void main(String[] args) {
        ClosestMeetingNode test = new ClosestMeetingNode();

        // 2
//        int[] arr = {1, 2, -1};
//        int a = 0;
//        int b = 2;

        // 2
//        int[] arr = {2, 2, 3, -1};
//        int a = 0;
//        int b = 1;

        // 2
//        int[] arr = {2, 2, 3, -1};
//        int a = 3;
//        int b = 1;

        // 3
        int[] arr = {5, 3, 1, 0, 2, 4, 5};
        int a = 3;
        int b = 4;

        int i = test.closestMeetingNode(arr, a, b);
        System.out.println(i);
    }

    public int closestMeetingNode(int[] edges, int node1, int node2) {
        if (node1 == node2) {
            return node2;
        }
        long a = find(node1, node2, edges);
        if (a == -1) {
            return -1;
        }
        long b = find(node2, node1, edges);
        int m1 = (int) (a >> 32);
        int m2 = (int) (b >> 32);
        int v1 = (int) a;
        int v2 = (int) b;
        if (m1 == m2) {
            return Math.min(v1, v2);
        }
        return m1 > m2 ? v2 : v1;
    }

    private long find(int node1, int node2, int[] edges) {
        Map<Integer, Integer> map = new HashMap<>(edges.length, 1);
        int count = 0;
        while (!map.containsKey(node1) && node1 != -1) {
            map.put(node1, count);
            node1 = edges[node1];
            count++;
        }
        count = 0;
        while (!map.containsKey(node2) && node2 != -1) {
            map.put(node2, -1);
            node2 = edges[node2];
            count++;
        }
        Integer v = map.get(node2);
        if (v == null || v == -1) {
            return -1L;
        }
        return ((long) Math.max(v, count) << 32) + node2;
    }

}
